import java.util.Arrays;

public class Test {


        public int minSubArrayLen(int target, int[] nums) {
            //二分查找
            int length = nums.length;
            int sum[] = new int[length + 1];

            int ans = Integer.MAX_VALUE;

            for(int i = 1;i < length + 1;i++){
                sum[i] = sum[i - 1] + nums[i - 1];
            }
            int bound = 0;
            for(int j = 1;j < length + 1;j++){

                int find = target + sum[j - 1];

                bound = BinarySearch(sum,find);

                if(bound < 0) bound = -bound - 1;
                if(bound <= length) ans = Math.min(ans,bound - j + 1);
            }

            return ans == Integer.MAX_VALUE ? 0 : ans;

        }

        private int BinarySearch(int[] sum,int find){
            int left = 0,right = sum.length -1;
            while(left <= right){
                int mid = left + (right - left) /2;

                if(sum[mid] > find){
                    right = mid -1;
                }else if(sum[mid] < find){
                    left = mid + 1;
                }else{
                    return mid;
                }
            }
            return -1;
        }

    public int minSubArrayLen1(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }


    public static void main(String[] args) {
        Test t = new Test();

        System.out.println(t.minSubArrayLen1(11, new int[]{1,2,3,4,5}));
        //2,3,1,2,4,3
    }
}

class Solution2 {
    public static int lengthOfLongestSubstring(String s) {
        if(s.length() == 0) return 0;

        char[] ch = s.toCharArray();

        int[] hash = new int[128];

        int left = 0,right = 0,ret = 1;

        while(right < ch.length){

            //1.进入窗口
            hash[ch[right]]++;
            //找到重复字符
            while(hash[ch[right]] > 1){
                //出窗口
                hash[ch[left++]]--;
            }
            //更新结果
            ret = Math.max(ret,right - left + 1);

            right++;
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(Solution2.lengthOfLongestSubstring("bbbbb"));
    }
}
